package com.zjsru.leetcode75.level1.tree;

/**
 * @Author: cookLee
 * @Date: 2023-12-14
 * 统计二叉树中好节点的数目
 * 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
 */
public class GoodNodes {
    /**
     * 主
     * \
     * 输入：root = [3,1,4,3,null,1,5]
     * 输出：4
     * 解释：图中蓝色节点为好节点。
     * 根节点 (3) 永远是个好节点。
     * 节点 4 -> (3,4) 是路径中的最大值。
     * 节点 5 -> (3,4,5) 是路径中的最大值。
     * 节点 3 -> (3,1,3) 是路径中的最大值。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(3, new TreeNode(1, new TreeNode(3), null), new TreeNode(4, new TreeNode(1), new TreeNode(5)));
        GoodNodes goodNodes = new GoodNodes();
        System.out.println(goodNodes.goodNodes(tree));
    }

    /**
     * 良好节点：bfs
     *
     * @param root 根
     * @return int
     */
    public int goodNodes(TreeNode root) {
        return this.bfs(root,Integer.MIN_VALUE);
    }

    /**
     * bfs
     * 深度优先搜索
     *
     * @param root  根
     * @param value 值
     * @return int
     */
    private int bfs(TreeNode root, int value) {
        if (root == null) {
            return 0;
        }
        int ans = 0;
        //叶子节点可能会和根节点相同
        if (root.val >= value) {
            ans++;
            value = root.val;
        }
        ans += this.bfs(root.left, value) + this.bfs(root.right, value);
        return ans;
    }

}
